#冒泡排序

def BubbleSort(nums: list):
    for i in range(len(nums)-1, 0, -1):
        for j in range(i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums


# a=BubbleSort([7,8,6,9,5,3,0,3])
# print(a)


#冒泡修改
"""
更改之后的冒泡排序
奇数次获得未确定序列中未排完的最大值的位置
但是偶数次获得未确定序列中未拍完的最小值的位置
适用于渴望单次获得最大值最小值的情况
"""

def BubbleSort2(lst: list):
    L, R = 0, len(lst)-1
    for j in range(len(lst)-1, 0, -1):
        if (j-len(lst)+1) %2:
            for i in range(R-1, L-1, -1):
                if lst[i+1] < lst[i]:
                    lst[i], lst[i+1] = lst[i+1], lst[i]
            L += 1
        else:
            for i in range(L, R, 1):
                if lst[i] > lst[i+1]:
                    lst[i], lst[i+1] = lst[i+1], lst[i]
            R -= 1
    return lst


#短冒泡
'''优化后的冒泡排序，升序
    最优时间复杂度为O(n)，比如L本身就是排好序的：[17, 20, 26, 31, 44, 54, 55, 77, 93]
    最坏时间复杂度还是O(n^2)
    '''

def shortBubbleSort(lst: list):
    l = len(lst)
    if l <= 1: return lst
    for i in range(l-1, 0, -1):
        flag = False
        for j in range(i):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                flag = True
        if not flag: return lst

